bisection.method {animation}R Documentation

Demonstration of the Bisection Method for Root-finding on an Interval

Description

In mathematics, the bisection method is a root-finding algorithm which works by repeatedly dividing an interval in half and then selecting the subinterval in which a root exists. This function gives a visual demonstration of this process of finding the root of an equation f(x) = 0.

Usage

bisection.method(FUN = function(x) x^2 - 4, rg = c(-1, 10), tol = 0.001,
    interact = FALSE, main, xlab, ylab, ...)

Arguments

FUN the function in the equation to solve (univariate)
rg a vector containing the end-points of the interval to be searched for the root; in a c(a, b) form
tol the desired accuracy (convergence tolerance)
interact logical; whether choose the end-points by cliking on the curve (for two times) directly?
xlab, ylab, main axis and main titles to be used in the plot
... other arguments passed to curve

Details

Suppose we want to solve the equation f(x) = 0. Given two points a and b such that f(a) and f(b) have opposite signs, we know by the intermediate value theorem that f must have at least one root in the interval [a, b] as long as f is continuous on this interval. The bisection method divides the interval in two by computing c = (a + b) / 2. There are now two possibilities: either f(a) and f(c) have opposite signs, or f(c) and f(b) have opposite signs. The bisection algorithm is then applied recursively to the sub-interval where the sign change occurs.

During the process of searching, the mid-point of subintervals are annotated in the graph by both texts and blue straight lines, and the end-points are denoted in dashed red lines. The root of each iteration is also plotted in the right margin of the graph.

Value

A list containing

root the root found by the algorithm
value the value of FUN(root)
iter number of iterations; if it is equal to ani.options('nmax'), it's quite likely that the root is not reliable because the maximum number of iterations has been reached

Author(s)

Yihui Xie

References

http://en.wikipedia.org/wiki/Bisection_method

http://animation.yihui.name/compstat:bisection_method

See Also

deriv, uniroot

Examples

# default example 
xx = bisection.method() 
xx$root  # solution

## Not run: 
 
# a cubic curve 
f = function(x) x^3 - 7 * x - 10 
xx = bisection.method(f, c(-3, 5)) 
# interaction: use your mouse to select the end-points 
bisection.method(f, c(-3, 5), interact = TRUE) 

# HTML animation pages 
ani.start(nmax = 50, ani.height = 400, ani.width = 600, interval = 1,
    title = "The Bisection Method for Root-finding on an Interval",
    description = "The bisection method is a root-finding algorithm
    which works by repeatedly dividing an interval in half and then
    selecting the subinterval in which a root exists.")
par(mar = c(4, 4, 1, 2))
bisection.method(main = "")
ani.stop() 

## End(Not run)

[Package animation version 1.0-1 Index]